public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.canCompleteCircuit(new int[]{1,2,3,4,5}, new int[]{3,4,5,1,2}));
        System.out.println(s.canCompleteCircuit(new int[]{2,3,4}, new int[]{1,1000,1}));
    }
}

//如果油不够，直接从无法到达的下一个加油站开始重新检查
//能环绕一周即存在解
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int count = 0;
        int start = 0;
        int cur = 0;
        int curGas = 0;
        while (count < n) {
            while (curGas + gas[cur] < cost[cur]) {
                if ((cur + 1) % n <= start) {
                    return -1;
                }
                count = 0;
                start = cur + 1;
                cur = start;
                curGas = 0;
            }
            curGas += gas[cur] - cost[cur];
            cur = (cur + 1) % n;
            count++;
        }
        return start;
    }
}
